import json
from typing import List
from alg import Solution  # 确保 alg.py 文件在同一个目录下

def load_test_data(filename: str) -> List[int]:
    """
    从文件中加载测试数据
    :param filename: 文件名
    :return: 测试数据
    """
    with open(filename, "r") as file:
        return json.load(file)

def verify_permutations(nums: List[int], permutations: List[List[int]]) -> bool:
    """
    验证生成的排列是否正确
    :param nums: 原始数组
    :param permutations: 生成的排列列表
    :return: 是否正确
    """
    # 检查排列的数量是否正确
    expected_count = 1
    for i in range(1, len(nums) + 1):
        expected_count *= i  # 计算阶乘
    if len(permutations) != expected_count:
        return False

    # 检查每个排列是否唯一且包含所有原始元素
    seen = set()
    for perm in permutations:
        if tuple(perm) in seen:
            return False
        seen.add(tuple(perm))
        if sorted(perm) != sorted(nums):
            return False

    return True

if __name__ == "__main__":
    # 加载测试数据
    filename = "test_data.json"
    test_data = load_test_data(filename)
    print(f"加载的测试数据: {test_data}")

    # 调用 permute 方法生成排列
    solution = Solution()
    permutations = solution.permute(test_data)
    print(f"生成的排列: {permutations}")

    # 验证排列是否正确
    if verify_permutations(test_data, permutations):
        print("排列验证通过！")
    else:
        print("排列验证失败！")

    # 输出排列的数量
    print(f"生成的排列数量: {len(permutations)}")